package leetcode.editor.cn.dp;

public class Test {
    public static int knapsackImplBy2DArray(int W, int N, int[] weights, int[] values) {
        // N 个物品， 0 到 N- 1 对应weight和values的长度
        // W背包大小，0 到 W， 数组则需要W + 1长度
        int[][] dp = new int[N][W + 1];
        // 初始化第一行第一列数据
        // 容量为0价值肯定为0
        for (int i = 0; i < N; i++) {
            dp[i][0] = 0;
        }
        // 放入第一个物品
        for (int j = 0; j < W + 1; j++) {
            // 容量大于第一个物品的重量
            if (j >= weights[0]) {
                dp[0][j] = values[0];
            }
        }
        // 基于初始化后的数据进行递推
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < W + 1; j++) {
                if (j >= weights[i]) {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i]] + values[i]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[N - 1][W];
    }

    public static int knapsackImplBy1DArray(int W, int N, int[] weights, int[] values) {
        int[] dp = new int[W + 1];

        for (int j = 0; j < W + 1; j++) {
            if (j >= weights[0]) {
                dp[j] = values[0];
            }
        }

        for (int i = 1; i < N; i++) {
            for (int j = W; j >= 0; j--) {
                if (j >= weights[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
                }
            }
        }
        return dp[W];
    }

    public static void main(String[] args) {
        int[] weights = {1, 3, 4, 2};
        int[] values = {15, 20, 30, 10};
        knapsackImplBy1DArray(6, 4, weights, values);
    }
}
